package algorithms.sort;

import java.util.Arrays;

import algorithms.Util;

/**
 * 插入排序<br>
 * 前i个元素已经是有序（一个元素自然是有序的）， <br>
 * 然后将第i+1个元素插入到前面有序序列中（从头遍历找到比自己大的元素，插入到前面）。<br>
 * 
 * <p>
 * 因为频繁的插入元素，使用数组需要频繁移到元素，带来性能开销,可以考虑使用链表进行优化<br>
 * 插入元素时寻找插入位置，从头遍历可以使用二分查找来优化性能； 但是二者不能共同使用。<br>
 * 可以使用二叉排序树优化性能。 @See algorithms.tree.BinarySearchTreeSort
 * </p>
 * 
 * @author shaoyuxia
 *
 * @param <T>
 */
public class InsertSort<T extends Comparable<T>> implements ISort<T> {

	@Override
	public T[] sort(T[] a) {
		return sortOptimized(a);
	}

	/**
	 * 此算法实现的思路是，待排序元素在有序序列中寻找插入位置，是从左往右遍历的，<br>
	 * 从左向右扫描时，如果数组的长度为n，插⼊位置为i，我们需要扫描前 ⾯i个元素，然后进⾏n − i +
	 * 1次移动，最后将x插入到第i个位置。也就是说，从左向右扫描会遍历整个数组。
	 * 
	 * 算法进行了O(n^2)次比较和O(n^2)次移动
	 * 
	 * @param a
	 * @return
	 */
	private T[] sort_original(T[] a) {
		int length = a.length;
		for (int i = 1; i < length; i++) { // 每轮插入一个元素到有序子集中
			// 判断是否需要插入
			if (a[i].compareTo(a[i - 1]) < 0) {
				T tmp = a[i];
				// 查找位置，然后一次性平移数组
				for (int j = 0; j < i; j++) { // 待插入元素寻找插入位置，这边可以使用二分查找法寻找位置来优化
					if (a[i].compareTo(a[j]) < 0) {
						// a[j]插入到a[i]前
						Util.rightMove(a, j, i - 1, 1);
						a[j] = tmp;
						break;
					}
				}
			}
		}
		return a;

	}

	/**
	 * 使二分查找后，比较次数变成了O(n lg n)， 但是移动次数还是O(n^2)
	 * 
	 * @param a
	 * @return
	 */
	private T[] sort_original_with_binarysearch(T[] a) {
		int length = a.length;
		for (int i = 1; i < length; i++) { // 每轮插入一个元素到有序子集中
			// 判断是否需要插入
			if (a[i].compareTo(a[i - 1]) < 0) {
				T tmp = a[i];
				// 查找位置，然后一次性平移数组
				int beginindex = Util.binarySearch(a, a[i], 0, i - 1);
				beginindex = beginindex == -1 ? 0 : beginindex;
				Util.rightMove(a, beginindex, i - 1, 1);
				a[beginindex] = tmp;
			}
		}
		return a;
	}

	/**
	 * 优化了插入逻辑，数组边移动边比较
	 * 
	 * 如果从右向左扫描，我们最多只需要检 查i个元素，并且⼀边扫描⼀边将元素向右移动。<br>
	 * 算法进行了O(n^2)次比较和O(n^2)次移动
	 * 
	 * @param a
	 * @return
	 */
	private T[] sortOptimized(T[] a) {
		int i, j;
		int length = a.length;
		for (i = 1; i < length; i++) {
			// 判断是否需要插入
			if (a[i].compareTo(a[i - 1]) < 0) {
				// 一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处
				T temp = a[i];
				for (j = i - 1; j >= 0 && a[j].compareTo(temp) > 0; j--)
					a[j + 1] = a[j];
				a[j + 1] = temp;
			}
		}
		return a;
	}

	public static void main(String[] args) {
		InsertSort<Integer> s = new InsertSort<>();
		Integer[] array = Util.generateArray(50000);
		Integer[] arraycopy = Arrays.copyOf(array, array.length);
		Integer[] arraycopy2 = Arrays.copyOf(array, array.length);

		long begin = System.currentTimeMillis();

		Util.print(array, 30);

		begin = System.currentTimeMillis();
		s.sort_original_with_binarysearch(array);
		System.out.println("used :" + (System.currentTimeMillis() - begin));

		Util.print(array, 30);

		Util.print(arraycopy, 30);

		begin = System.currentTimeMillis();
		s.sort_original(arraycopy);
		System.out.println("used :" + (System.currentTimeMillis() - begin));

		Util.print(arraycopy, 30);
		Util.print(arraycopy2, 30);

		begin = System.currentTimeMillis();
		s.sortOptimized(arraycopy2);
		System.out.println("used :" + (System.currentTimeMillis() - begin));

		Util.print(arraycopy2, 30);
	}
}
